﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_94_InorderTraversal
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class MainProject
    {
        static void Main(string[] args)
        {
            //TreeNode treeNode = new TreeNode(3, new TreeNode(1, null, null), new TreeNode(2, null, null));
            TreeNode treeNode = new TreeNode(3, new TreeNode(1, null, null), new TreeNode(2, null, null));
            //Console.WriteLine(IsPalindrome(0));
            IList<int>  vs = InorderTraversal(treeNode);
            foreach (var item in vs)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }

        public static IList<int> InorderTraversal(TreeNode root)
        {
            IList<int> vs = new List<int>();
            if (root!=null)
            {
                GetMiddleValue(root, vs);
            }
            return vs;
        }

        public static void GetMiddleValue(TreeNode treeNode, IList<int> vs)
        {
            if (treeNode==null)
            {
                return;
            }
            GetMiddleValue(treeNode.left, vs);
            vs.Add(treeNode.val);
            GetMiddleValue(treeNode.right, vs);
        }

        public static void GetMiddleValue1(TreeNode treeNode, IList<int> vs)
        {
            if (treeNode.left!=null)
            {
                GetMiddleValue(treeNode.left, vs);
                vs.Add(treeNode.val);
                if (treeNode.right != null)
                {
                    GetMiddleValue(treeNode.right, vs);
                }
            }
            else
            {
                vs.Add(treeNode.val);
                if (treeNode.right!=null)
                {
                    GetMiddleValue(treeNode.right, vs);
                }
            }
        }
    }
}
